<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      var fib = function (n) {
        // 方法一：递归（）---时间O（2^n）（）---空间：O（n）（递归深度）
        // if (n === 0) {
        //   return 0;
        // } else if (n === 1) {
        //   return 1;
        // } else {
        //   return fib(n - 1) + fib(n - 2);
        // }

        // 方法二：加缓存（在leetcode时间没降低，空间还多了，应该是测试数据比较少吧）---时间O（n）（每个数只计算一次）---空间：O（n）（）
        // let map = {};
        // let result = 0;
        // if (n === 0) {
        //   return 0;
        // } else if (n === 1) {
        //   return 1;
        // } else {
        //   if (map[n]) {
        //     return map[n];
        //   }
        //   result = fib(n - 1) + fib(n - 2);
        //   map[n] = result;
        //   return result;
        // }

        // 方法三：循环（）---时间O（n）（）---空间：O（n）（）
        // let arr = [];
        // arr[0] = 0;
        // arr[1] = 1;
        // for (let i = 2; i <= n; i++) {
        //   arr[i] = arr[i - 1] + arr[i - 2];
        // }
        // return arr[n];

        // 方法四：尾递归（）---时间O（1）（）---空间：O（n）（）
        // return wei(n);
        // function wei(n, a = 0, b = 1) {
        //   if (n === 0) {
        //     return a;
        //   }
        //   if (n === 1) {
        //     return b;
        //   }
        //   return wei(n - 1, b, a + b);
        // }

        // 方法五：循环只记录前两个数字（）---时间O（n）（）---空间：O（1）（）
        let pre = 1;
        let pre_pre = 0;
        if (n === 0 || n === 1) {
          return n;
        }
        for (let i = 3; i <= n; i++) {
          const temp = pre_pre
          pre_pre = pre;
          pre = pre + temp;
        }
        return pre + pre_pre;
      };
      console.log(fib(2));
      console.log(fib(4));
    </script>
  </body>
</html>
